//给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？ 
//
// 以任意顺序返回这两个数字均可。 
//
// 示例 1: 
//
// 输入: [1]
//输出: [2,3] 
//
// 示例 2: 
//
// 输入: [2,3]
//输出: [1,4] 
//
// 提示： 
//
// 
// nums.length <= 30000 
// 
// Related Topics位运算 | 数组 | 哈希表 
//
// 👍 99, 👎 0 
//
//
//
//

package leetcode.editor.day;

// 面试题 17.19. 消失的两个数字
// https://leetcode.cn/problems/missing-two-lcci/
class MissingTwoLcci {
    public static void main(String[] args) {
        Solution solution = new MissingTwoLcci().new Solution();
        solution.missingTwo(new int[]{1});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] missingTwo(int[] nums) {
            // 剑指 Offer 56 - I. 数组中数字出现的次数变形
            // 将1~n的数字再加入一次，就可以所有2个数中找到出现一次的数，和56一模一样
            int n = 0, x = 0, y = 0, m = 1;
            int max = nums.length + 2;
            // 先异或一遍 1~n
            for (int i = 1; i <= max; i++) {
                n ^= i;
            }
            // 再异或一遍原始数组
            for (int num : nums) {
                n ^= num;
            }

            // 找出最后一位不为0
            while ((n & m) == 0) {
                m <<= 1;
            }

            // 对最后一位不为0进行分组
            for (int i = 1; i <= max; i++) {
                if ((i & m) != 0) x ^= i;
                else y ^= i;
            }

            for (int num : nums) {
                if ((num & m) != 0) x ^= num;
                else y ^= num;
            }

            return new int[]{x, y};
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
